\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}
\sloppy

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}


\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 5}

\paragraph{Задание 1.} Мы положили тысячу рублей в банк под пять процентов годовых. В начале каждого года мы докладываем пятьсот рублей на счет. Сколько денег будет на счете через $n$ лет?

\begin{Solution}
Размер счета описывается простым реккурентным соотношением $a_n = 1.05 a_{n-1} + 500$, при начальных условиях $a_0 = 1000$. Посмотрим на первые несколько членов последовательности:
\begin{itemize}
\item $a_0 = 1000$

\item $a_1 = 1000 \cdot 1.05 + 500$

\item $a_2 = a_1 \cdot 1.05 + 500 = \left(1000\cdot 1.05 + 500\right) \cdot 1.05 + 500 = 1000 \cdot 1.05^2 + 500 \cdot \left(1.05 + 1\right)$

\item $a_i = a_0 \cdot 1.05^i + \sum_{k=0}^{i-1} 500 \cdot 1.05^k= a_0 \cdot 1.05^i + 500 \frac{1-1.05^{i}}{1-1.05}$

\end{itemize}
\end{Solution}

\paragraph{Задание 2.} Пусть $2n$ игроков принимают участие в тенисном турнире. Определить с использованием рекуррентного соотношения число $a_n$ различных пар, которые можно сформировать для $n$ матчей первого круга.

\begin{Solution}
Пусть у нас есть $n$ пар, зафиксируем произвольного игрока из $2n$, выбрать ему пару можно $2n-1$ способами. Всех остальных $2n-2$ игроков можно разбить по парам $a_{n-1}$ способами, получили рекуррентное соотношение:
\[
	\begin{split}
		& a_n = \left(2n - 1\right) a_{n-1} \\
		& a_1 = 1
	\end{split}
\]
далее попробуем выразить общую формулу:
\[
	\begin{split}
		& \frac{a_n}{a_{n-1}} = 2n-1 \\
		& \frac{a_n}{a_{n-2}} = \frac{a_n}{a_{n-1}} \frac{a_{n-1}}{a_{n-2}} = \left(2n-1\right) \left(2 \left(n-1\right) - 1\right) \\
		& ... \\
		& \frac{a_n}{a_1} = \prod_{i=0}^{n-1} \left(2\left(n-i\right)-1\right) = a_n
	\end{split}
\]
\end{Solution}

\paragraph{Задание 3.} Определить с помощью рекуррентного соотношения число $a_n$ областей, на которые забивается плоскость с помощью $n$ окружностей так, что любые из этих окружностей пересекаются ровно по двум точкам и что никакие из трех окружностей не имеют общей точки пересечения.

\begin{Solution}
Для начал рассмотрим первые несколько таких разбиений, например до 5 окружностей. Получаем следующую последовательность $a_1 = 2$, $a_2 = 4$, $a_3 = 8$, $a_4 = 14$, $a_5 = 22$, и рассмотрим разницу между соседними числами последовательности, получаем следующую последовательность $2, 4, 6, 8$. Идея рассмотрения разницы заключается в следующем, каждая вновь добавленая окружность уеличивает количество областей ровно на столько, сколько старых областей она пересекает (т. е. каждая пересеченная область делится линией окружности попалам), каждая следующая окружность как видно пересекает на 2 области больше чем предыдущая, получаем рекуррентное соотношение:
\[
	a_n = a_{n-1} + 2 \cdot (n-1)
\]
Если раскрутить формулу для первых значений $n$, можно увидеть, что получаем сумму 2 и арифметической прогрессии от 2 до $2\left(n-1\right)$ с шагом 2, тогда можно ывести замкнутую формулу:
\[
	a_n = n^2 - n + 2
\]
проверим формулу подстановкой в рекуррентное соотношение:
\[
	n^2 - n + 2 = {\left(n-1\right)}^2 - n + 1 + 2 + 2 \cdot \left(n - 1\right) = n^2 - 2\cdot n + 1 - n + 3 + 2\cdot n - 2 = n^2 - n + 2
\]
\end{Solution}

\paragraph{Задание 4.} Рассмотрим плоскость $\left(x,y\right)$. Предположим, что мы можем ходить по плоскости, делаяя шаг верх $U$, шаг право $R$ и шаг влево $L$ на единицу длины так, чтобы шаг $R$ не следовал за шагом $L$ и наоборот (так называемые решеточные пути на плоскости). Пусть $a_n$, $a_0=1$ - число таких путей после $n$ шагов. Найти $a_n$.

\begin{Solution}
Как я понял задание, $a_n$ - количество всех путей длинны $n$, исходящих из одной точки и удовлетворяющих условиям выше. Теперь введем несколько обозначений, $U_n$ - количество путей длинны $n$ из данной точки, при условии, что пришли мы в нее снизу (т. е. из данной точки мы можем пойти в три стороны), а $L_n,R_n$ - количество путей из данной точки при условии, что мы пришли в нее слева или справа, соответственно. Тогда условие задачи состоит в отыскании $U_n$. Составим рекуррентные соотношения:
\[
	\begin{split}
		& U_n = R_{n-1} + L_{n-1} + U_{n-1} \\
		& R_n = R_{n-1} + U_{n-1} \\
		& L_n = L_{n-1} + U_{n-1}
	\end{split}
\]
Из соотношений выше видно, что $R_n$ и $L_n$ - симметричны, и соответственно $R_n = L_n$, т. е. соотношения преобразуются следующим образом:
\[
	\begin{split}
		& U_n = 2 R_{n-1} U_{n-1} \\
		& R_n = R_{n-1} + U_{n-1}
	\end{split}
\]
Теперь выразим $R_{n-1}$ из первого выражения и подставим во второе:
\[
	\begin{split}
		& R_{n-1} = \frac{U_n - U_{n-1}}{2} \Rightarrow \frac{U_{n+1} - U_n}{2} = \frac{U_n - U_{n-1}}{2} + U_{n-1} \Leftrightarrow \\
		& \Leftrightarrow U_{n+1} = 2 U_n + U_{n-1}
	\end{split}
\]
Видно, что требуется уже 2 начальных условия, одно $U_0 = 1$, а второе не трудно построить $U_1 = 3$.
Составляем характеристическое уравнение:
\[
	\begin{split}
		& r^2 - 2 r - 1 = 0 \\
		& r_{1,2} = 1 \pm \sqrt{2}
	\end{split}
\]
Решение ищем в виде $U_n = C_1 r_1^n + C_2 r_2^n = C_1 {\left(1+\sqrt{2}\right)}^n + C_2 {\left(1 - \sqrt{2}\right)}^n$, исходя из начальных условий получаем систему уравнений:
\[
	\begin{split}
		& 1 = C_1 + C_2 \\
		& 3 = C_1 \left(1 + \sqrt{2}\right) + C_2 \left(1 - \sqrt{2}\right)
	\end{split}
\]
откуда получаем:
\[
	\begin{split}
		& C_1 = \frac{\sqrt{2} + 2}{2\sqrt{2}} \\
		& C_2 = \frac{\sqrt{2} - 2}{2 \sqrt{2}}
	\end{split}
\]
\end{Solution}

\paragraph{Задание 5.} Космический зонд обнаружил, что органическое вещество на Марсе имеет ДНК, состоящее из пяти символов $\left(a,b,c,d,e\right)$; четыре пары симолов - $ce, cd, ed, ee$ - никогда не встречаются в марсианских ДНК, однако любая цепочка, не содержащая этих пар возможна. Порядок букв в цепочке важен, поэтому, например, цепочка $bbdca$ возможна, а $bbcda$ - нет. Найти рекуррентные соотношения, которым удовлетворяют эти цепочки слов.

\begin{Solution}
Ввведем обозначения, количество цепочек ДНК длинны $n$ которые могут начинаться слюбого символа обозначем через $I_n$, цепочки ДНК длинны $n$ которые не могут начинаться с символов $e$ или $d$ обозначим через $I_n^{e,d}$. Тогда можно сказать, что количество всех цепочек ДНК длинны $n$ складывается из количества цепочек ДНК длинны $n-1$, перед которыми стоят символы $a$, $b$ или $d$, плюс количество цепочек ДНК длинны $n-1$ перед которыми стоят символы $c$ или $e$, т. е. те цепочки, которые не могут начинаться с $e$ или $d$, в итоге имеем:
\[
	\begin{split}
		& I_n = 3 I_{n-1} + 2 I_{n-1}^{e,d} \\
		& I_{n}^{e,d} = 2 I_{n-1} + I_{n-1}^{e,d}
	\end{split}
\]
Второе уравнение вытекает из того, что цепочки, которые не могут начинаться с $e$ или $d$, могут начинаться с $a$, $b$ или $c$, причем на цепочки начинающиеся с $c$ опять же накладываются ограничения.
Теперь выразим из первого уравнения $I_{n-1}^{e,d}$:
\[
	I_{n-1}^{e,d} = \frac{I_{n-1} - 3 I_n}{2}
\]
Подставляем во второе уравнение и в конечном итоге получаем:
\[
	I_{n+1} = I_{n-1} + 4 I_n
\]
Далее задаем начальные условия:
\[
	\begin{split}
		& I_0 = 1 \\
		& I_1 = 5 \\
	\end{split}
\]
далее проверяем правильна ли формула для следующих значений:
\[
	\begin{split}
		& I_2 = 1 + 4 \cdot 5 = 21 \\
		& I_3 = 5 + 4 \cdot 21 = 89
	\end{split}
\]
(Оба варианта я проверил, действительно, все правильно).
Характеристическое уравнение:
\[
	\begin{split}
		& r^2 - 4 r - 1 = 0 \\
		& r_{1,2} = 2 \pm \sqrt{5}
	\end{split}
\]
Ищем общее решение в виде $I_n = C_1 r_1^n + C_2 r_2^n = C_1 {\left(2 + \sqrt{5}\right)}^n + C_2 {\left(2 - \sqrt{5}\right)}^n$, для этого решем систему:
\[
	\begin{split}
		& 1 = C_1 + C_2 \\
		& 5 = C_1 \left(2 + \sqrt{5}\right) + C_2 \left(2 - \sqrt{5}\right)
	\end{split}
\]
получаем решение:
\[
	\begin{split}
		& C_1 = \frac{\sqrt{5} + 3}{2\sqrt{5}} \\
		& C_2 = \frac{\sqrt{5} - 3}{2\sqrt{5}}
	\end{split}
\]
\end{Solution}

\paragraph{Задание 6.} В осеннем семестре у преподавателя $n$ рабочих дней. Семестр поделен учебным управлением на две части. Первая часть (первые $k$ дней, $1 \le k \le n-2$) посвящена теории, вторая часть (последние $n-k$ дней) отводятся на практические занятия. В первой части семестра преподаватель може выбрать один из рабочих дней и уехать в командировку. Во второй части он может выбрать любые два рабочих дня для поездки на конференцию. Сколькими способами преподаватель может выбрать эти дни в осеннем семестре? Как изменится ответ, если он в каждой из частей может выбрать любое количество дней на командировки?

\begin{Solution}
В первом случае ответ очевиден из $k$ дней первой части преподаватель может выбрать 1 ровно $k$ способами, а из $n-k$ дней торой части преподаватель может выбрать 2 ровно $\binom{n-k}{2}$ способами, итого:
\[
	k \cdot \binom{n-k}{2}
\]
Теперь рассмотрим случай, когда преподаватель может выбрать произвольное количество дней в каждой части семестра, если в первой части семестра $k$ дней, то количество вариантов выбора $i$ дней из $k$ равно $\binom{k}{i}$, получаем последовательность чисел (при $i = \overline{0,k}$), запишем эту последоательность следующим образом:
\[
	A_1 = \binom{k}{0} + \binom{k}{1}x + \binom{k}{2}x^2 + ... + \binom{k}{k} x^k = \sum_{i=0}^{k} \binom{k}{i}x^i = {\left(1+x\right)}^k
\]
аналогичным образом получаем выражение для второй части семестра:
\[
	A_2 = \binom{n-k}{0} + \binom{n-k}{1}x + \binom{n-k}{2}x^2 + ... + \binom{n-k}{n-k} x^{n-k} = {\left(1+x\right)}^{n-k}
\]
В каждой части семестра дни можно выбирать независимо, т. е. для каждого выбора дней из первой части семестра (выбора коэффициента при $x$ в $A_1$) мы можем выбрать любое доступное количество дней из второй части семестра (опять же выбрать коэффициент при любой степени $x$ в $A_2$). Например, выберем в $A_1$ некоторый член последовательности $a_i$ и зафиксируем его, количество способов выбрать дни в семестре так, чтобы в первой части выбралось $a_i$ дней определяется выражением:
\[
	a_i \left(\binom{n-k}{0} + \binom{n-k}{1} + ... + \binom{n-k}{n-k}\right) = a_i \sum_{t=0}^{n-k} \binom{n-k}{t}
\]
или переходя к форме записи в виде многочлена:
\[
	a_i x^i \sum_{t=0}^{n-k} \binom{n-k}{t} x^t
\]
а по всем $a_i$:
\[
	\sum_{i=0}^k \left(x^i \binom{k}{i} \sum_{t=0}^{n-k} \binom{n-k}{t} x^t\right)
\]
т. е. в точности произведение двух многочленов:
\[
	\begin{split}
		& {\left(1+x\right)}^k \cdot {\left(1+k\right)}^{n-k} = {\left(1+x\right)}^n = \\
		& = \sum_{i=0}^n \binom{n}{i} x^i
	\end{split}
\]
где при $x^i$ согласно правилам перемножения многочленов стоит количество способов выбрать $i$ дней в семестре. Теперь необходимо просуммировать все коэффициенты при полученном многочлене, чтобы получить все возможные варианты выбора дней в семестре, в виде производящих функций это делается умножением на $\frac{1}{1-x}$, но в данном конкретном случае это мало полезно. Легче просто воспользоваться известным соотношением:
\[
	\sum_{i=0}^n \binom{n}{i} = 2^n
\]
Что можно получить и другим более простым способом - каждый день может быть выбран или не выбран преподавателем, всего дней $n$, значит вариантов выбора дней ровно $2^n$.
\end{Solution}

\paragraph{Задание 7.} Объяснить комбинаторный смысл произведения дух обыкновенных производящих функций.

\begin{Solution}
Постараюсь показать его на примере задачи о целочисленных решениях уравнения $a_1 + a_2 = m$. Пусть имется произодящая функция:
\[
	f\left(x\right) = b_0 + b_1 x + b_2 x^2 + ... + b_n x^n
\]
Тогда квадрат производящей функции: ${\left(f\left(x\right)\right)}^2$ будет являться производящей функцией для количества решений уравнения, причем интересующий нас коэффициент будет стоять при $x^m$. Кроме того можно сказать, что в таком случае будут рассматриваться только слагаемые $\le n$, т. к. старшая степень производящей функции равна $n$.

Рассмотрим почему это так. Для простоты пусть $n \ge m$. Коэффициент при $x^m$ в результате перемножения будет получена как сумма следующего вида:
\[
	b_0 b_m + b_1 b_{m-1} + b_2 b_{m-2} + ... + b_m b_0
\]
т. е. сумма произведений коэффициентов при $x^k$ и $x^i$ причем только таких, что $k+i=m$, т. е. в точности все варианты разложения числа $m$ при условии $b_i = 1$. Также в таком виде легко добавить ограничения, например, если $a_1 > 0$, тогда будем рассматриввать произведение следующих производящих функций:
\[
	\begin{split}
		& f\left(x\right) = 0 + c_1 x + c_2 x^2 + ... \\
		& g\left(x\right) = b_0 + b_1 x + b_2 x^2 + ...
	\end{split}
\]
т. е. все слогаемые в которых присутствует $c_0$ просто обнуляться и не внесут вклад в результат, аналогично и для ограничений сверху, например, пусть $a_2 < k$, тогда рассматриваем произведение следующих производящих функций:
\[
	\begin{split}
		& f\left(x\right) = c_0 + c_1 x + c_2 x^2 + ... \\
		& g\left(x\right) = b_0 + b_1 x + b_2 x^2 + ... + b_{k-1} x^{k-1}
	\end{split}
\]
т. е. ограничение сверху или снизу есть просто условие на количество членов формального ряда (тут опять же в условиях задачи $c_i,b_j = 1$ при $j<k$).
\end{Solution}

\paragraph{Задание 8.} В футбольной команде $n$ игроков. Тренер разбивает команду на две группы и просит каждую из групп выстроиться в линию. Затем он первой группе игроков раздает красные футболки. Во второй группе любой из игроков может выбрать футболку одного из трех цветов - оранжевую, белую или зеленую. Сколько существует различных способов таких разбиений команды?

\begin{Solution}
Рассмотрим экспоненциальную производящую функцию следующего вида:
\[
	f\left(x\right) = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + ...
\]
в квадрате этой производящей функции коэффициент при $\frac{x^i}{i!}$ равен $\sum_{k=0}^i \binom{i}{k}$ т. е. количество способов выбрать из $i$ $k$ элементов, или разбить $i$-множество на 2 подмножества $k$-подмножество и $i-k$-подмножество. Возведем полученную функцию в кадрат еще раз, полученная производящая функция так же будет экспоненциальной и при $\frac{x^i}{i!}$ в ней будет стоять следующий коэффициент:
\[
	a_i = \sum_{k=0}^i \left(\binom{i}{k} \sum_{j=0}^k \binom{k}{j} \sum_{t=0}^{i-k} \binom{i-k}{t}\right)
\]
выбор из $i$-множества $k$-множества, а затем выбор из $k$-множества $j$-множества и из $i-k$-множества $t$-множества разбивает исходное $i$-множество на 4 подмножества (с мощностями $j, k-j, t, i-k-t$), а коэффициент $a_i$ - количество всех таких разбиений соответственно, таким образом можно предположить, что коэфициент $a_i$ произведения экспоненциальных производящих функций показывает количество разбиений $i$-множества.

Заметим теперь, что:
\[
	e^x = f\left(x\right) = 1 + x + \frac{x^2}{2} + ... + \frac{x^i}{i!} + ...
\]
и тогда итоговое выражение можно посчитать как:
\[
	{\left(e^x\right)}^4 = e^{4x} = 1 + 4x + \frac{4^2 x^2}{2} + ... + \frac{4^i x^i}{i!} + ...
\]

И для команды из $n$ человек решением будет коэффициент при $\frac{x^n}{n!}$, но теперь вспомним, что не были учтено, что комнада первоначально делится на две группы, и логично предположить, что группы не пустые, а значит людей с футболками красного цвета не нулевое количество, и кроме того их меньше $n$, тогда поправим одну производящуюю функцию следующим образом:
\[
	e^x - 1 = x + \frac{x^2}{2} + \frac{x^3}{3!} + ...
\]
а произведение трех других:
\[
	e^{3x} - 1 = 3 x + \frac{3^2 x^2}{2} + \frac{3^3 x^3}{3!} + ...
\]
Результат:
\[
	g\left(x\right) = \left(e^x - 1\right) \left(e^{3x} - 1\right) = e^{4x} - e^{3x} - e^x + 1
\]
преобразовывая к экспоненциальной производящей функции:
\[
	g\left(x\right) = 0 + 0 x + \frac{\left(4^2 - 3^2 - 1\right) x^2}{2} + \frac{\left(4^3 - 3^3 - 1\right) x^3}{3!} + ...
\]

Далее можно проверить правильность первых коэффициентов, действительно поделить команду из 0 или 1 человека на 2 группы нельзя, далее для команды из 2 человек возможно 6 вариантов (три сочетания цветов футболки плюс перестановка двух игроков), для трех все уже сложнее.
\end{Solution}

\end{document}
